import com.sun.xml.internal.ws.client.sei.ResponseBuilder;

import java.beans.beancontext.BeanContext;

/**
 * Created by L.jp
 * Description:给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
 * 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *

 * User: 86189
 * Date: 2023-02-06
 * Time: 23:54
 */
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
public class Solution {
    //这是二叉搜索树的最近公共祖先，二叉搜索树的特点就是所有根节点的值大于左子树节点值小于右子树节点值，这一特点对于搜索有很大的效率
    //二叉搜索树的特点就是左边的节点一定比root小，右边的节点一定比root大，所以pq其中一个大于root,一个小于root，那么公共祖先就是根节点，这个和普通二叉树找公共祖先的方法不一样
    //解题思路：如何找公共祖先，肯定不能通过pq节点的下标找，这是没有下标的，所以我们自顶向下找，通过二叉搜索树的规则来找到公共祖先root
    /*public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root != null) {
           if(root.val<p.val && root.val<q.val){  //pq节点在root节点右边
               root=root.right;
           }else if(root.val>p.val && root.val > q.val ){
               root= root.left;     //pq节点在root节点右边
           }else {
               break;
           }
        }
        return root;
    }*/
    
    
    //递归解法
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val<p.val && root.val<q.val){  //pq节点在root节点右边
            return lowestCommonAncestor(root.right,p,q);
        }
        if(root.val>p.val && root.val > q.val ) {
            return lowestCommonAncestor(root.left, p, q);  //pq节点在root节点右边
        }
        return root;
    }
}
